Advent of Code 2020: Day 5

Advent of Code Day 5 wasn’t too difficult but it was a fun exercise. You’re given a bunch of airplane tickets, where the row and seat number is given as a string of 10 characters. The airplane has a total of $128$ rows and $8$ seats in each row. The first seven characters of the ticket halve the amount of possible rows, once for each character. An F indicates that the seating is in the first half of possibilities and a B indicates that the seating is in the second half of possibilities. By halving the amount of rows $7$ times the exact row of the ticket is found as $128 / (2^7) = 1$. For the seat, only three characters are needed: An L indicates left half and R indicates right half. For example the ticket FBFBBFFRLR indicates exactly row 44, column 5 by the following logic:

                                    Row 0-127   Seat 0-7
[F] B  F  B  B  F  F  R  L  R       Row 0-63    Seat 0-7
 F [B] F  B  B  F  F  R  L  R       Row 32-63   Seat 0-7
 F  B [F] B  B  F  F  R  L  R       Row 32-47   Seat 0-7
 F  B  F [B] B  F  F  R  L  R       Row 40-47   Seat 0-7
 F  B  F  B [B] F  F  R  L  R       Row 44-47   Seat 0-7
 F  B  F  B  B [F] F  R  L  R       Row 44-45   Seat 0-7
 F  B  F  B  B  F [F] R  L  R       Row 44      Seat 0-7

 F  B  F  B  B  F  F [R] L  R       Row 44      Seat 4-7
 F  B  F  B  B  F  F  R [L] R       Row 44      Seat 4-5
 F  B  F  B  B  F  F  R  L [R]      Row 44      Seat 5

Part 1

In part 1 of the challenge we simply have to find the highest ID of the tickets provided. This ID is given as $ID=R\cdot8+C$ where $R$ is the row number and $C$ is the column number. In order to do this, I calculate the position of every ticket (807 tickets in my input). The function below splits a list of rows (or columns) in half and returns the correct one based on the character. I.e. if the character is Forward or Left it returns the first half, otherwise it returns the latter.

1
2
3
4
5
6

def split(rows, char):
    splits = np.split(rows, 2)  # Splits into two equal sized arrays
    if char == "F" or char == "L":
        return splits[0]
    else:
        return splits[1]

A second function creates a list of rows and of columns and repeatedly calls this function, that is, 7 times for the row listing and 3 times for the column.

1
2
3
4
5
6
7
8

def get_position(partition):
    rows = np.arange(0, 128)
    columns = np.arange(0, 8)
    for rp in partition[:-3]:
        rows = split(rows, rp)
    for cp in partition[-3:]:
        columns = split(columns, cp)
    return np.array((rows, columns)).T

This produces an array of size $807 \times 2$ and using numpy broadcasting I can easily multiply all rows with $8$ and take their sum.

1
2

positions = np.concatenate([get_position(p) for p in passes])
seat_ids = np.sort(np.sum(positions * [8, 1], axis=1))

The answer to part 1 is the maximum seat ID, which is easily found by max().

Part 2

The description for part two on the website is sufficient to explain this part:

It’s a completely full flight, so your seat should be the only missing boarding pass in your list. However, there’s a catch: some of the seats at the very front and back of the plane don’t exist on this aircraft, so they’ll be missing from your list as well. Your seat wasn’t at the very front or back, though; the seats with IDs +1 and -1 from yours will be in your list.

I could just iterate over it and find the missing one, but keeping in line with the numpy broadcasting, I decided on a super speed solution. I’ll explain my code by example: Assume ID’s $3 … 8$ are present except for your ID, $6$. First I make sure the list of seat ID’s are sorted. Then I find the minimum and maximum of that list and generate another list, with every number from minimum to maximum (not inclusive). I then take their difference

Seating ID's    Array   Difference
3               3       0
4               4       0
5               5       0
7               6       1
8               7       1

The moment a seat is missing the difference becomes 1. The numpy function argmax() finds the index at which this first occurs, and the answer becomes the seat ID at this index minus 1.

The full code for this day can be found here. The entire repository is available at GitHub.